package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2022/1/27.<br><br>
 *
 * 中等：乘积最大子数组
 */
public class Topic152 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        int[] array = new int[] {2,3,-2,4};
        System.out.println(solution.maxProduct(array));

        array = new int[] {-2,0,-1};
        System.out.println(solution.maxProduct(array));
    }

    private interface BaseSolution {
        int maxProduct(int[] nums);
    }

    private static class Solution1 implements BaseSolution {

        @Override
        public int maxProduct(int[] nums) {
            int len = nums.length;
            int[] maxArray = new int[len];
            int[] minArray = new int[len];
            maxArray[0] = minArray[0] = nums[0];

            for(int i = 1; i < len; i++) {
                maxArray[i] = Math.max(maxArray[i - 1] * nums[i], Math.max(nums[i], minArray[i - 1] * nums[i]));
                minArray[i] = Math.min(minArray[i - 1] * nums[i], Math.min(nums[i], maxArray[i - 1] * nums[i]));
            }

            int result = maxArray[0];
            for(int i = 1; i < len; i++) {
                result = Math.max(result, maxArray[i]);
            }
            return result;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int maxProduct(int[] nums) {
            int max, min, result;
            max = min = result = nums[0];

            int len = nums.length;
            for(int i = 1; i < len; i++) {
                int tempMax = max;
                max = Math.max(max * nums[i], Math.max(nums[i], min * nums[i]));
                min = Math.min(min * nums[i], Math.min(nums[i], tempMax * nums[i]));
                result = Math.max(max, result);
            }
            return result;
        }
    }
}
